package com.duing.greedy;

import java.util.Arrays;

// 分发饼干
public class FindContent {

    public static void main(String[] args) {
        int[] g = {2, 3};
        //int[] s = {1, 1, 2, 4};
        //int[] s = {1, 1, 1, 1};
        int[] s = {2, 3, 4};
        System.out.println(findContentChildren(g, s));
    }

    // 饼干的大小刚刚好满足胃口较小的孩子
    // g = [1,2], s = [1,2,3]

    // 饼干的大小 能满足 依次大于胃口较小的孩子
    // g = [1,2], s = [2,3,4]

    // g[i]       s[j]
    // g = [2,3], s = [1,1,2,4]
    // g = [2,3], s = [1,1,1,1]

    // 保证数组的有序  孩子胃口从小到大排列  饼干尺寸从小到大排列
    // 先让胃口最小的孩子  获取到能满足的饼干
    // 本质 用相对最小的饼干 满足胃口相对最小的孩子

    // 时间复杂度  m  n
    //    排序   O(mlogm) O(nlogn)
    //    贪心   O(m)     O(n)
    //          O(m(logm+1))  O(n(logn+1))
    //          O(mlogm) + O(nlogn)
    // 空间复杂度  O(logm) + O(logn)
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int gLen = g.length;
        int sLen = s.length;

        int count = 0;
        for (int i = 0, j = 0; i < gLen && j < sLen; i++, j++) {
            // 在s中 查找满足 g中最小胃口孩子的饼干
            while (j < sLen && s[j] < g[i]) {
                System.out.println(j + "," + s[j]);
                j++;
            }
            // 只要不是因为数组遍历完 退出的循环  代表就是找到了饼干
            if (j < sLen) {
                System.out.printf("i=%d,j=%d,g[%d]=%d,s[%d]=%d", i, j, i, g[i], j, s[j]);
                System.out.println();
                count++;
            }
        }
        return count;
    }
}
